package showtime.framework.algorithm.graph
{
	/**
	 * @project Dijkstra
	 * @date 2011-9-19
	 * @author 绿豆蛙
	 * 
	 */
	public class Grapher
	{ 
		
		private var maxver:int = 0;
		private var maxium:int = 1000000;
		
		private var state:Array = null;
		private var dist:Array = null;
		private var path:Array = null;
		private var edge:Array = null;
		
		public function Grapher(maxver:int)
		{
			this.maxver = maxver;	
			
			initializeComponents();
		}
		
		public function registerEdge(u:int, v:int, cost:int, undirected:Boolean = false):void
		{
			edge[u][v] = cost;
			
			if (undirected)
			{
				edge[v][u] = cost;
			}
		}
		/**
		 * 构建邻接矩阵。
		 *  
		 * @param nodeAmount
		 * @return 
		 * 
		 */		
		private function initializeComponents():void
		{
			state = new Array(maxver);
			dist = new Array(maxver);
			path = new Array(maxver);
			edge = new Array(maxver);			
			
			for (var i:int = 0; i < maxver; i++)
			{
				edge[i] = new Array(maxver);
				state[i] = 0;
				dist[i] = 0;
				path[i] = 0;
				for (var j:int = 0; j < maxver; j++)
				{
					edge[i][j] = 0;
				}
			}

		}
		
		public function getResult(nodeID:int):Shortest
		{
			var result:Shortest = new Shortest();
			result.nodes = [];
			
			var shortest:Array = new Array(maxver);
			
			for (var i:int = 0; i < maxver; i++)
			{
				shortest[i] = 0;
			}
			
			var k:int = 0;
			shortest[k] = nodeID;
			result.cost = dist[nodeID];
			
			while (path[shortest[k]] != -1)
			{
				k++;
				shortest[k] = path[shortest[k - 1]];
			}

			for (var j:int = k; j > 0; j--)
			{
				result.nodes.push(shortest[j]);
			}
			
			result.nodes.push(shortest[0]);
			
			return result;
		}
		/**
		 *  
		 * @param nodeAmount 节点数。
		 * @param edge 邻接矩阵。
		 * 
		 */		
		public function dijkstra(v0:int):void
		{			
			var i:int = 0;
			var j:int = 0;
			var k:int = 0;

			for (i = 0; i < maxver; i++)
			{
				for (j = 0; j < maxver; j++)
				{
					if (i == j)
					{
						edge[i][j] = 0;
					}
					else if (edge[i][j] == 0)
					{
						edge[i][j] = maxium;
					}
				}
			}
			
			for (i = 0; i < maxver; i++)
			{
				dist[i] = edge[v0][i];
				state[i] = 0;
				
				if (i != v0 && dist[i] < maxium)
				{
					path[i] = v0;
				}
				else
				{
					path[i] = -1;
				}
			}
			
			state[v0] = 1; dist[v0] = 0;
			
			for ( i = 0; i < maxver - 1; i++)
			{
				var min:int = maxium;
				var u:int = v0;
				
				for (j = 0; j < maxver; j++)
				{
					if (!state[j] && dist[j] < min)
					{
						u = j;
						min = dist[j];
					}
				}
				
				state[u] = 1;
				
				for (k = 0; k < maxver; k++)
				{
					if (!state[k] && edge[u][k] < maxium && dist[u] + edge[u][k] < dist[k])
					{
						dist[k] = dist[u] + edge[u][k];
						path[k] = u;
					}
				}
			}
		}
		
		
	}
}